package com.github.hgkmail.hello.leetcode101.pointer.tree;

import com.github.hgkmail.hello.leetcode101.base.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class LC112PathSum2 {
    public void dfs(TreeNode node, int currSum, Deque<Integer> aCase, List<List<Integer>> res) {
        if (node==null) {
            return;
        }
        if (node.val==currSum && node.left==null && node.right==null) {
            List<Integer> t=new ArrayList<>(aCase);
            t.add(node.val);
            res.add(t);
            return;
        }
        aCase.addLast(node.val);
        dfs(node.left, currSum-node.val, aCase, res);
        dfs(node.right, currSum-node.val, aCase, res);
        aCase.removeLast();
    }

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> aCase = new ArrayDeque<>();
        dfs(root, targetSum, aCase, res);

        return res;
    }

    public static void main(String[] args) {

    }
}
